#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;

class Solution {
private:
    void solve(int idx,vector<int>& candidates, int sum, int target, 
                vector<int>&sub_ans, vector<vector<int>>& ans, map<vector<int>, int>& mp){
        if(sum > target) return;
        else if(sum == target && mp.count(sub_ans)==0){
            ans.push_back(sub_ans);
            mp[sub_ans] = 1;
            return;
        }
        for(; idx<candidates.size(); ++idx){
            //前一个状态包含后一个状态
            if(sum + candidates[idx] > target) break;
            sub_ans.push_back(candidates[idx]);
            solve(idx+1, candidates, sum+candidates[idx], target, sub_ans, ans, mp);
            sub_ans.pop_back();

            //pruning
            while(idx+1<candidates.size() && candidates[idx] == candidates[idx+1]) ++idx;
        }
    }
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        vector<vector<int>> ans;
        vector<int> sub_ans;
        map<vector<int>, int> mp;
        sort(candidates.begin(), candidates.end());
        //impossible
        if(candidates.empty()) return ans;
        if(candidates[0]>target) return ans;

        //recursion to compute the answer
        solve(0, candidates, 0, target, sub_ans, ans, mp);

        return ans;
    }
};

int main(){

}